Today, handwriting is becoming an increasingly popular method for inputting data to data handling units, especially to mobile phones and Personal Digital Assistants (PDAs). In order to handle the inputted data, the handwriting must be recognized and interpreted. Most existing methods for recognizing handwriting require that the characters that are to be inputted be written one by one and are separately recognized. An example of such a method is provided in U.S. Pat. No. 4,731,857, but a commonly known example is Graffiti®, manufactured by Palm, Inc.
In order to speed up input of data it is desired that cursive handwriting is allowed. However, recognition of cursive handwriting is more complex than recognition of separate characters. The increase in complexity for cursive handwriting recognition may be attributed to the problem of segmenting connected characters, i.e. to identify the transition from one character to another within the handwritten pattern. Errors in cursive handwriting recognition may hence come in two levels, that is errors in segmentation and errors in recognition of the separated characters, which greatly complicate the construction of a lucid sequential recognition system.
Methods for recognition of cursive handwriting generally suffer from the problem that there are many possible segmentations between adjacent characters which results in a large number of possible segmentations of a handwritten pattern.
Most commercial systems today employ complicated statistical systems using neural networks and hidden markov models with integrated dictionaries. Examples of such systems are presented in P. Neskovic and L. Cooper, “Neural network-based context driven recognition of on-line cursive script”, Seventh International Workshop on Frontiers in Handwriting Recognition Proceedings, p. 352-362, September 2000 and M. Schenkel and I. Guyon, “On-line cursive script recognition using time delay networks and hidden Markov models”, Machine Vision and Applications, vol. 8, pages 215-223, 1995. A problem with these systems is that they are large and require large training sets. Furthermore they are highly dependent on the dictionary used.
A dictionary may be used for improving the result of a recognition by making an evaluation of the probability that different recognitions of the handwritten pattern are correct. Thus, results from a recognition of a handwritten pattern may be compared to a dictionary for discarding results that are not present in the dictionary. This improves the probability that a correct recognition result may be presented to a user. In D. Y. Chen, J. Mao and K. M. Mohiuddin, “An efficient algorithm for matching a lexicon with a segmentation graph”, Proceedings of the Fifth International Conference on Document Analysis and Recognition, pages 543-546, 1999, a method of comparing a dictionary to segmentation candidates is disclosed. However, this method gets slower as the size of the dictionary is increased. Another method is disclosed in S. Lucas, “Efficient best-first dictionary search given graph-based input”, 15th International Conference on Pattern Recognition, vol. 1, pages 434-437, 2000. This method presents a more efficient way to retrieve a best recognition that is present in the dictionary. The dictionary retrieval is achieved by computing a path algebra, which requires that the segmentation of the handwritten pattern is established first.
In WO 02/37933, a method for handwritten word recognition using a dictionary is disclosed. The method creates an interpretation graph, which comprises vertices representing segmentation points and edges representing an interpretation of the segment between the segmentation points. A search procedure is applied on the segmentation points in order to construct the graph and, thus, to determine a word recognition. The search procedure is performed to look back on previous segmentation points to determine whether to place an edge/segment in the graph. Thus, at each vertex, a list of word level hypotheses may be stored. Further, in order to trim the hypothesis list, a matching with a dictionary may be performed. For each allowed character class, the search procedure needs to determine, at each segmentation point, whether it is feasible to place an edge/segment corresponding to the character class in the graph. This requires heavy computations in order to perform the search procedure and, thus, the method is slow.